#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.


"""
每个海岛群类似于无向图中的一个连通分量.
"""


class Solution:
    """
    @param grid: an integer matrix
    @return: an integer
    """
    ISLAND = 1
    CITY = 2
    def numIslandCities(self, grid):
        # Write your code here
        self.rows, self.cols = len(grid), len(grid[0])
        self.visited = self.make_matrix(self.rows, self.cols, False)
        self.grid = grid

        self.pre = {}          # {row, col : pre}
        self.root_is_city = {} # {row, col : true/false}
        self.city_count = 0

        for row in range(self.rows):
            for col in range(self.cols):
                self.handle(row, col)

        return self.city_count

    def handle(self, r, c):
        # 比较上, 左: if 1, 2: 查找左上 pre, 做union
        # union时, 需要减少count数量
        # print('handle', r, c)
        if r < 0 or r > self.rows or c < 0 or c > self.cols:
            return

        if self.grid[r][c] == 0:
            return

        # self.find_pre()
        self.pre[(r, c)] = (r, c)
        if r-1 >= 0 and self.grid[r-1][c] != 0:
            print('match', r, c)
            self.pre[ (r, c) ] = self.find_pre(r-1, c)
            print('match find', r, c, self.pre[(r, c)], self.pre)
            # if not self.is_city( self.pre[ (r-1, c) ]) and self.grid[r][c] == 2:
            if not self.is_city( self.find_pre( r-1, c )) and self.grid[r][c] == 2:
                self.root_is_city[self.pre[ (r, c) ]] = True
                print("+= 1 up ", r, c)
                self.city_count += 1
        elif self.grid[r][c] == 2:
            # 自立门户
            self.root_is_city[self.pre[ (r, c) ]] = True
            print("+= 1 iso ", r, c)
            self.city_count += 1

        if c-1 >= 0 and self.grid[r][c-1] != 0:
                col_pre = self.find_pre(r, c-1)
                if self.find_pre( r, c ) != col_pre:
                    print('pppp union', r, c, self.find_pre( r, c ), col_pre, self.pre)
                    self.union( self.pre[(r, c)], col_pre )

    def union(self, n1, n2):
        assert n1 != n2

        print('union', n1, n2)
        if self.is_city(n2):
            if self.is_city(n1):
                print('----=', n1, n2)
                self.city_count -= 1        # 合并了
            else:
                self.root_is_city[n1] = True

        print('union pre', n2, n1)
        self.pre[n2] = n1

    def is_city(self, node):
        # pre = self.find()
        # return bool( self.root_is_city.get(node) )
        pre_node = self.find_pre(*node)
        print("is_city", node, pre_node)
        return bool( self.root_is_city.get(pre_node) )

    def find_pre(self, r, c):
        # print('find_pre', r, c)
        if r < 0 or r > self.rows or c < 0 or c > self.cols:
            return -1

        node = (r, c)
        # 没有到顶
        pre_node = self.pre[node]
        # print('pre_node', pre_node)
        # print('pres', self.pre)
        if node != pre_node:
            # print(node, pre_node, node == pre_node)
            # node = pre_node
            self.pre[node] = self.find_pre(*pre_node)

        return self.pre[node]       # 这里非常容易出现bug



    def make_matrix(self, rows, cols, init_value=None):
        one_row = [init_value] * cols
        return [list(one_row) for i in range(rows)]


def main():
    print("start main")
    s = Solution()

    mat = [
         [1,1,1,1,0],
         [1,1,0,0,1],
         [0,0,1,1,1],
         [0,0,0,0,0],
         [1,0,2,0,1]
    ]
    # mat = [
    #      [1,1,0,0,0],
    #      [0,1,0,0,1],
    #      [0,0,0,1,1],
    #      [0,0,0,0,0],
    #      [0,0,0,0,1]
    # ]
    ret = s.numIslandCities(mat)
    print(ret)
    # print(s.root_is_city)

if __name__ == "__main__":
    main()
